package com.wujunshen.algorithm.sort;

import lombok.extern.slf4j.Slf4j;
import org.apache.commons.lang3.RandomUtils;

/**
 * @author frank woo(吴峻申) <br>
 *     email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2020/7/19 01:57<br>
 */
@Slf4j
public class ShellSort {
  public static int[] shellSort(int[] sortArray) {
    return shellSort(sortArray, RandomUtils.nextInt());
  }

  public static int[] shellSort(int[] sortArray, int step) {
    // step为步长，每次减为原来的step分之一
    for (int groupNumber = sortArray.length / step; groupNumber > 0; groupNumber /= step) {
      // 共groupNumber个组，对每一组都执行插入排序
      for (int i = 0; i < groupNumber; i++) {
        insertSort(sortArray, groupNumber, i);
      }
    }
    return sortArray;
  }

  /**
   * 循环中其实执行的都是插入排序
   *
   * <p>具体实现做法可以@see #com.wujunshen.algorithm.sort.InsertSort
   *
   * @param sortArray 待排序数组
   * @param groupNumber 分组数
   * @param index 索引
   */
  private static void insertSort(int[] sortArray, int groupNumber, int index) {
    int temp;
    for (int j = index + groupNumber; j < sortArray.length; j += groupNumber) {
      // 如果sortArray[j] < sortArray[j-groupNumber]，则寻找sortArray[j]位置，并将后面数据的位置都后移
      if (sortArray[j] < sortArray[j - groupNumber]) {
        temp = sortArray[j];
        int k = j - groupNumber;
        while (k >= 0 && sortArray[k] > temp) {
          sortArray[k + groupNumber] = sortArray[k];
          k -= groupNumber;
        }
        sortArray[k + groupNumber] = temp;
      }
    }
  }
}
